package main

import (
	"fmt"
	"math"
	"sort"
)

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	t := -100000000
	// 遍历每个元素，作为三元组的第一个元素
	if len(nums) == 3 {
		return nums[0] + nums[1] + nums[2]
	}
	for i := 0; i < len(nums)-2; i++ {
		// 跳过重复的元素
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		// 使用双指针在剩余部分寻找符合条件的两个数
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if int(math.Abs(float64(target-sum))) <= target-t {
				// 找到一个符合条件的三元组
				t = sum

				// 移动左指针，跳过重复元素
				left++
				for left < right && nums[left] == nums[left-1] {
					left++
				}

				// 移动右指针，跳过重复元素
				right--
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum < target {
				// sum < 0，说明需要增大sum
				left++
			} else {
				// sum > 0，说明需要减小sum
				right--
			}
		}
	}
	return t

}

func main() {
	//fmt.Println(threeSumClosest([]int{-1, 2, 1, -4}, 1))
	fmt.Println(threeSumClosest([]int{-4, 2, 2, 3, 3, 3}, 0))
}
